﻿#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric> 
#include <stack>
using namespace std;
typedef long long ll;


//class Solution {
//public:
//    bool hasSameDigits(string s) {
//        int n = s.size();
//        while (n > 2) {
//            string ss;
//            for (int i = 0; i < n - 1; i++) {
//                int x = s[i] - '0', y = s[i + 1] - '0';
//                int tmp = (x + y) % 10;
//                ss += tmp + '0';
//            }
//            s = ss;
//            n = ss.size();
//        }
//        return s[0] == s[1];
//    }
//}; 

//class Solution {
//public:
//    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
//        priority_queue<long long>ok;
//        int n = grid.size();
//        for (int i = 0; i < n; i++) {
//            int m = grid[i].size();
//            sort(grid[i].begin(), grid[i].end());
//            while (limits[i]--) {
//                ok.push(grid[i][--m]);
//                if (!m)
//                    break;
//            }
//        }
//        long long ans = 0;
//        while (k--) {
//            long long tmp = ok.top();
//            ok.pop();
//            ans += tmp;
//        }
//        return ans;
//    }
//}; 


//class Solution {
//public:
//    bool hasSameDigits(string s) {
//        int n = s.size();
//        int sum = 0;
//        for (int i = 1; i < n - 1; i++) {
//            sum += s[i] - '0';
//        }
//        int x = (s[0] - s[n - 2] + sum * 2) % 10;
//        int y = (s[n - 1] - s[1] + sum * 2) % 10;
//        return x == y;
//    }
//}; 


//class Solution {
//public:
//    bool hasSameDigits(string s) {
//        int n = s.size();
//        vector<int> dp(n + 1);
//        for (int i = 0; i < n; i++) {
//            dp[i] = s[i] - '0';
//        }
//        for (int i = 1; i < n - 1; i++) {
//            for (int j = 0; j < n - i; j++) {
//                dp[j] = (dp[j] + dp[j + 1]) % 10;
//            }
//        }
//        return dp[0] == dp[1];
//    }
//};






//class Solution {
//public:
//    int len(vector<int> a, vector<int>b) {
//        int len = abs(a[0] - b[0]) + abs(a[1] - b[1]);
//        return len;
//    }
//    bool check(int m, vector<vector<int>>& points, int k) {
//        int n = points.size();
//        int cnt = 0;
//        for (int i = 0; i < n - 1; i++) {
//            for (int j = i + 1; j < n; j++) {
//                if (len(points[i], points[j]) >= m)
//                    cnt++;
//            }
//        }
//        cout << "cnt=" << cnt << '\n';
//        return cnt >= k;
//    }
//    int maxDistance(int side, vector<vector<int>>& points, int k) {
//        int l = 0, r = 2*side, m;
//        cout << "r=" << r << '\n';
//        while (l < r) {
//            m = (l + r + 1) >> 1;
//            cout << "m=" << m << ' ';
//            if (check(m, points, k))
//                l = m;
//            else
//                r = m - 1;
//        }
//        return l;
//    }
//};
//int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    Solution solve;
//    int x = 2;
//    vector<vector<int>>p = { {0,0},{0,1},{0,2},{1,2},{2,0},{2,2},{2,1} };
//    solve.maxDistance(x, p, 5);
//    return 0;
//}



//int n, k;
//int x[1005], y[1005];
//int f[1005];
//double ans;
//
//double way(int i, int j) {
//	return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
//}
//
//int find(int x) {
//	return f[x] == x ? x : f[x] = find(f[x]);
//}
//
//bool check(double m) {
//	for (int i = 1; i <= n; i++) {
//		f[i] = i;
//	}
//	for (int i = 1; i < n; i++) {
//		for (int j = i + 1; j <= n; j++) {
//			int fi = find(i), fj = find(j);
//			if (fi != fj&& way(i, j) <= m) {
//				f[fi] = fj;
//			}
//		}
//	}
//	int cnt = 0;
//	for (int i = 1; i <= n; i++) {
//		if (find(i) == i)
//			cnt++;
//	}
//	//时隔五天，我™的终于发现在这道题我错在哪了；
//	return cnt >= k;
//}
//
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++) {
//		cin >> x[i] >> y[i];
//	}
//	double l = 0, r = 20000, mid;
//	double eps = 1e-4;
//	while (l+eps < r) {
//		mid = (l + r) / 2.0;
//		if (check(mid)) {
//			l = mid;
//		}
//		else {
//			r = mid;
//		}
//	}
//	printf("%.2f", l);
//	return 0;
//}


//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n, m;
//        cin >> n >> m;
//
//        vector<vector<int>> a(n, vector<int>(m));
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < m; ++j) {
//                cin >> a[i][j];
//            }
//        }
//
//        vector<int> hasColor(n * m, 0);
//        vector<int> hasBad(n * m, 0);
//
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < m; ++j) {
//                int color = a[i][j] - 1;
//                hasColor[color] = 1;  
//                if (i + 1 < n && a[i][j] == a[i + 1][j]) {
//                    hasBad[color] = 1;  
//                }
//             
//                if (j + 1 < m && a[i][j] == a[i][j + 1]) {
//                    hasBad[color] = 1; 
//                }
//            }
//        }
//
//        int sumColor = accumulate(hasColor.begin(), hasColor.end(), 0);
//        int sumBad = accumulate(hasBad.begin(), hasBad.end(), 0);
//        int maxBad = *max_element(hasBad.begin(), hasBad.end());
//        cout << sumColor + sumBad - 1 - maxBad << endl;
//    }
//    return 0;
//}

//
//int n, m;
//char a[1005][1005];
//int f[1005];
//int ans;
//
//int cot() {
//	stack<int> st;
//	int tmp = 0;
//	for (int i = 1; i <= m+1; i++) {
//		while (!st.empty() && f[st.top()] >= f[i]) {
//			int now = st.top();
//			st.pop();
//			int l = st.empty() ? -1 : st.top();
//			int r = i;
//			tmp = max(tmp, f[now] * (r - l - 1));
//		}
//		st.push(i);
//	}
//	return tmp;
//}
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cin >> a[i][j];
//		}
//	}
//
//	for (int i = 1; i <= m; i++) {
//		if (a[1][i] == 'F')
//			f[i] = 1;
//	}
//	ans = max(ans, cot());
//	for (int i = 2; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			if (a[i][j] == 'F')
//				f[j] += 1;
//			else
//				f[j] = 0;
//		}
//		ans = max(ans, cot());
//	}
//	cout << ans * 3 << ' ';
//
//	return 0;
//}